package interview.simulate;

import java.util.*;
import java.util.stream.Collectors;

/**
 * DNS本地缓存系统 https://blog.codefun2000.com/company/hw/22-9-23/P1164.html
 */
public class DnsCacheSystem {

    /**
     * 使用一个HashSet缓存URL，使用一个PriorityQueue记录CacheUrl过期时间，按过期时间的最小堆，然后模拟更新
     */
    static int curTime = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int capacity = sc.nextInt();//DNS缓存空间大小
        int urlNum = sc.nextInt();//待请求的URL的数量
        int[] urlArr = new int[urlNum];
        for (int i = 0;i < urlNum;i++)
            urlArr[i] = sc.nextInt();

        int tlsLen = sc.nextInt();
        HashMap<Integer, Integer> ttlMap = new HashMap<>();//Map<url, ttl>
        for (int i = 1;i <= tlsLen;i++)
            ttlMap.put(sc.nextInt(), sc.nextInt());

        List<Integer> result = new ArrayList<>();
        DnsCache dnsCache = new DnsCache(capacity);
        for (int i = 0;i < urlNum;i++, curTime++) {
            int url = urlArr[i];
            if (dnsCache.containsUrl(url))
                result.add(0);
            else {
                result.add(1);
                dnsCache.addUrlCache(url, ttlMap.getOrDefault(url, 5) + curTime);
            }
        }
        System.out.println(result.stream().map(Object::toString).collect(Collectors.joining(" ")));
    }

    public static class DnsCache {
        private final PriorityQueue<CacheUrl> dnsUrlQueue = new PriorityQueue<>();
        private final HashSet<Integer> dnsCache = new HashSet<>();
        private final int capacity;
        DnsCache(int capacity) {this.capacity = capacity;}

        public boolean containsUrl(int url) {
            while (dnsUrlQueue.peek() != null && dnsUrlQueue.peek().expireTime <= curTime) {
                CacheUrl cacheUrl = dnsUrlQueue.poll();
                dnsCache.remove(cacheUrl.url);
            }
            return dnsCache.contains(url);
        }

        public void addUrlCache(int url, int expireTime) {
            if (capacity > 0 && dnsUrlQueue.size() == capacity) {
                CacheUrl cacheUrl = dnsUrlQueue.poll();
                dnsCache.remove(cacheUrl.url);
            }
            dnsUrlQueue.offer(new CacheUrl(url, expireTime, curTime));
            dnsCache.add(url);
        }

        public static class CacheUrl implements Comparable<CacheUrl> {
            int url;
            int addTime;
            int expireTime;

            CacheUrl(int url, int expireTime, int addTime) {
                this.url = url;
                this.addTime = addTime;
                this.expireTime = expireTime;
            }

            @Override
            public int compareTo(CacheUrl o2) { //先根据过期时间比较，若过期时间相等则按加入缓存的时间比较
                if (this.expireTime - o2.expireTime == 0) return this.addTime - o2.addTime;
                return this.expireTime - o2.expireTime;
            }
        }
    }
}
